/*************************************************************************
> File Name: shell_sort.c
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2023-07-22 10:46:18
> Description: 希尔排序--特殊的插入排序
************************************************************************/

#include "general.h"
#include <stdio.h>

int shellSort(int arr[], int length);
int main(int argc, char const *argv[])
{
    int arr[] = {9, 4, 2, 7, 5, 1, 8, 3, 6, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArr(arr, size);
    shellSort(arr, size);
    printf("Sorted array: \n");
    printArr(arr, size);
    return 0;
}

int shellSort(int arr[], int length)
{
    int gap = length >> 2; // 增量初始为长度的一半
    int target = 0;
    int j = 0;
    int i = 0;
    while (gap > 0)
    {
        for (i = gap; i < length; i++)
        {
            target = arr[i]; // 取出目标值
            //*******************在子数组插入排序*******************
            j = i - gap; // 起点值
            while (j >= 0 && arr[j] > target)
            {
                arr[j + gap] = arr[j]; // 往后移动一个基准值的距离
                j -= gap;
            }
            arr[j + gap] = target; // 插入目标值
        }
        gap = gap >> 1; // 增量减半
    }
}